package com.dataStructure.sort;

public class Quick {

    public int[] sortArray(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }
        process( nums,  0,  nums.length - 1);
        return nums;
    }

    public void process(int[] nums, int left, int right) {
        if (left  >= right) {
            return;
        }
        int[] p = protition(nums, left, right);

        process(nums, left, p[0]);
        process(nums, p[1], right);

    }

    public int[] protition(int[] nums, int left, int right) {
        int base = nums[left];

        int i = left;
        while (i <= right) {
            if (nums[i] < base) {
                swap(nums, left ,i);
                left ++;
                i++;
            }
            else if (nums[i] == base) {
                i++;
            }
            else {
                swap(nums, i, right);
                right --;
            }
        }
        return new int[] {left - 1, right + 1};
    }

    public void swap(int[] nums, int i , int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
